package com.yhk.sort;

/**
 * @version 1.0
 * @Author moresuo
 * @Date 2024/10/31 11:40
 * @注释 排序算法
 */
public class Sort {

    /**
     * 选择排序
     * @param nums
     */
    public static void selectSort(int[] nums) {
        int n=nums.length;
        //起始下标
        int sortedIndex=0;
        for (int i = sortedIndex; i < n; i++) {
            int minIndex=i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex=j;
                }
            }
            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
        }
    }

    /**
     * 选择排序稳定版
     * @param nums
     */
    public static void selectSortStable(int[] nums) {
        int n=nums.length;
        int startIndex=0;
        for (int i = startIndex; i < n; i++) {
            int minIndex=i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex=j;
                }
            }
            //记录最小值
            int min = nums[minIndex];
            //将startIndex..minIndex的元素向后移
            for (int k = minIndex; k > i; k--) {
                nums[k] = nums[k - 1];
            }
            //将min替换至startIndex上
            nums[i]=min;
        }
    }

    /**
     * 冒泡排序
     * @param nums
     */
    public static void bubbleSort(int[] nums) {
        int n=nums.length;
        int startIndex=0;
        for (int i = startIndex; i < n; i++) {
            boolean isSwap=false;
            for (int j = n - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                    isSwap=true;
                }
            }
            //没有进行交换，说明之前就是有序地，直接提前结束排序
            if (!isSwap) {
                return;
            }
        }
    }

    /**
     * 插入排序
     * @param nums
     */
    public static void insertSort(int[] nums) {
        int n=nums.length;
        int startIndex=0;
        for (int i = startIndex; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                }else{
                    break;
                }
            }
        }
    }

    /**
     * 希尔排序
     * @param nums
     */
    public static void shellSort(int[] nums) {
        int n=nums.length;
        int startIndex=0;
        int h=1;
        while (h < n / 2) {
            h=h*2;
        }
        while (h >= 1) {
            startIndex=h;
            for (int i = startIndex; i < n; i++) {
                for (int j = i; j - h >= 0; j -= h) {
                    if (nums[j] < nums[j - h]) {
                        swap(nums, j, j - h);
                    }
                }
            }
            h/=2;
        }
    }

    /**
     * 堆排序
     * @param nums
     */
    public static void heapSort(int[] nums) {
        int n=nums.length;
        //建立大顶堆
        for (int i = 0; i < n; i++) {
            maxHeapSwim(nums, i);
        }
        //已经建立了大顶堆，直接将堆顶元素与最后一个元素进行交换
        while (n >= 1) {
            //交换堆顶元素
            swap(nums, 0, n - 1);
            n--;
            //下沉，重新构建大顶堆
            maxHeapSink(nums, 0, n);
        }
    }

    private static void maxHeapSink(int[] heap,int node,int size) {
        int left=(node * 2) + 1;
        int right=(node*2)+2;
        while (left<size||right<size) {
            int max=node;
            if (left < size && heap[max] < heap[left]) {
                //交换
                max=left;
            }
            if (right < size && heap[max] < heap[right]) {
                max=right;
            }
            //如果node就是最大的，直接返回
            if (node == max) {
                break;
            }
            //交换位置
            swap(heap, max, node);
            node=max;
            left=node*2+1;
            right=node*2+2;
        }
    }

    /**
     * 大顶堆上浮
     * @param heap
     * @param node
     */
    private static void maxHeapSwim(int[] heap, int node) {
        int parent=(node-1)/2;
        while (node > 0 && heap[node] > heap[parent]) {
            //交换子父节点
            swap(heap, node, parent);
            //上浮
            node=parent;
            parent=(node-1)/2;
        }
    }


    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j]=temp;
    }

    public static void main(String[] args) {
        int[] nums = {32, 5, 67, 12, 99, 2, 34, 55, -12};
        //selectSortStable(nums);
        //selectSort(nums);
        //bubbleSort(nums);
        //insertSort(nums);
        //shellSort(nums);
        heapSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+"\t");
        }
    }
}
